package bTree.LeetCode;

import java.util.*;

public class 课程表 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int count = 0;//实时记录度数为0的节点数
        int[] degree = new int[numCourses];
        Map<Integer, List<Integer>> map = new HashMap<>();
        //计算如度数和路径关系
        for (int i = 0; i < prerequisites.length; i++) {
            int from = prerequisites[i][1];
            int to = prerequisites[i][0];
            degree[to]++;
            if (!map.containsKey(from)) {
                map.put(from, new ArrayList<>());

            }
            map.get(from).add(to);
        }
        Queue<Integer>queue=new LinkedList<>();
        //初始化加入入度为0的节点
        for (int i = 0; i < degree.length; i++) {
            if (degree[i]==0){
                queue.add(i);
            }
        }
        while (!queue.isEmpty()){
            Integer peek = queue.peek();
            count++;
            List<Integer> list = map.get(peek);
            if (null!=list) {
                for (Integer i : list) {
                    degree[i]--;
                    if (degree[i] == 0) {
                        queue.add(i);
                    }
                }
            }
            queue.poll();
        }
        return count==numCourses;
    }
}